package pro.softzhang.algo.lc0;


import pro.softzhang.algo.flag.knowledge.KDynamicPlanning;

import java.util.LinkedList;
import java.util.List;

/**
 * 22. 括号生成
 * https://leetcode.cn/problems/generate-parentheses/
 */
@KDynamicPlanning
public class LC22_GenerateParentheses {
    public static void main(String[] args) {

    }

    static
    class Solution {
        public List<String> generateParenthesis(int n) {
            List<String> r = new LinkedList<>();
            doGenerateParenthesis(n, n, "", r);
            return r;
        }

        private void doGenerateParenthesis(int left, int right, String parenthesis, List<String> r) {
            if(left == 0 && right == 0) {
                r.add(parenthesis);
                return;
            }

            if(left > 0) {
                doGenerateParenthesis(left - 1, right, parenthesis + "(", r);
            }

            if(left < right) {
                doGenerateParenthesis(left, right - 1, parenthesis + ")", r);
            }
        }
    }

    static
    class Solution1 {
        public List<String> generateParenthesis(int n) {
            List<String> res = new LinkedList<>();
            char[] path = new char[n * 2];
            dfs(0, 0, n, path, res);
            return res;
        }

        private void dfs(int left, int right, int n, char[] path, List<String> res) {
            if (right == n) {
                res.add(new String(path));
                return;
            }

            if (left < n) {
                path[left + right] = '(';
                dfs(left + 1, right, n, path, res);
            }

            if (right < left) {
                path[left + right] = ')';
                dfs(left, right + 1, n, path, res);
            }
        }
    }
}
